package com.mgq.algorithm.forcerecursive;

/**
 * @author MaGuangQi
 * 汉诺塔问题
 * 汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,
 * 在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。
 * 并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
 * 版权声明：本文为CSDN博主「Rnan-prince」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
 * 原文链接：https://blog.csdn.net/qq_19446965/article/details/81591945
 * @date 2022-01-06 14:20
 **/
public class Hanno {
    public static void process(int i, String from, String to, String other) {
        if (i == 1) {//base case
            System.out.println("move "+i+ " from "+from+" to "+to);
            return;
        }
        //把i-1个盘子从from 移动到other
        process(i-1,from,other,to);
        //把i从from移动到to(直接打印)
        System.out.println("move "+i+ " from "+from+" to "+to);
        //把i-1个从other移动到to
        process(i-1,other,to,from);
    }

    public static void hanno(int n) {
        if (n < 0) {
            return;
        }
        process(n, "左","右", "中" );
    }
    public static void main(String[] args) {
        hanno(3);
    }
}
